#pragma once

#include "iostream"
#include "vector"
#include "algorithm"
#include "TypeDefin.h"
using namespace std;
/*HJJ QQ479287006
 *给你一棵 完全二叉树 的根节点 root ，求出该树的节点个数。

完全二叉树 的定义如下：在完全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层，则该层包含 1~ 2h 个节点。

 

示例 1：


输入：root = [1,2,3,4,5,6]
输出：6
示例 2：

输入：root = []
输出：0

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/count-complete-tree-nodes
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * */

//方式一 和方式二 使用递归前中后便利 遍历一次num+1 不在叙述

//方式二 还是递归 算另类吧 每层的左子树+右子树个数
int countNodes(TreeNode *root) {
    if (!root)
        return 0;
    int left = countNodes(root->left);
    int right = countNodes(root->right);

    return left + right + 1;
}

int countNodes(TreeNode *root) {
    if (root == nullptr) return 0;
    TreeNode *left = root->left;
    TreeNode *right = root->right;
    int leftHeight = 0, rightHeight = 0; // 这⾥初始为0是有⽬的的，为了下⾯求指数⽅便
    while (left) { // 求左⼦树深度
        left = left->left;
        leftHeight++;
    }

    while (right) { // 求右⼦树深度
        right = right->right;
        rightHeight++;
    }

    if (leftHeight == rightHeight) {
        return (2 << leftHeight) - 1;   //如果是满二叉树直接计算 求高度了 注意(2<<1) 相当于2^2，所以leftHeight初始为0
    }

    return countNodes(root->left) + countNodes(root->right) + 1;
}
